package cn.jdemo.algorithm.dynamicProgramming;

/**
 * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。
 * 你也可以先购买，然后在 同一天 出售。
 * 返回 你能获得的 最大 利润 。
 *
 * --- 可多次买卖
 * 动态规划
 * 1.定义+推导公式
 *  dp[i][0],第i天持有最大利润
 *      第i天不持有股票，则买入,dp[i-1][1] - price[i]
 *      第i天持有股票，则不可以买入,dp[i-1][0]
 *  --- dp[i][0] = max(dp[i-1][1] - price[i],dp[i-1][0])
 *  dp[i][1],第i天不持有最大利润
 *      第i天不持有股票，则不可卖出，那么当天利润是 dp[i-1][1]
 *      第i天持有股票，则卖出 dp[i-1][0] + price[i]
 *  --- dp[i][1] = Max(dp[i-1][1],dp[i-1][0] + price[i])
 * 2.初始化
 *      dp[0][0] = -prices[0];
 *      dp[0][1] = 0;
 * 3.样例
 *      dp[i][0]  dp[i][1]
 *    0     -7      0
 *    1     -1      0
 *    2     -1      4
 *    3     1       4
 *    4     1       7
 *    5     3       7
 *
 */
public class Stock2 {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        // int[] prices = {7,6,4,3,1};
        int res = new Stock2().maxProfit(prices);
        System.out.println(res);
    }

    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp0 = new int[length][2];
        int[][] dp1 = new int[length][2];
        dp0[0][0] = -prices[0];
        dp1[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp0[i][0] = Math.max(dp0[i - 1][0], dp1[i - 1][1] - prices[i]);
            dp1[i][1] = Math.max(dp1[i - 1][1], dp0[i - 1][0] + prices[i]);
        }
        return dp1[length-1][1];
    }

}
